Backtracking

利用各種可得的限制來做搜尋目標中的偷吃步

八皇后問題：西洋棋盤上任意擺放八個皇后彼此都不互攻的情況有幾種？

若想著把每一種任意擺放可能性列出來，再來挑選可行的盤面，
將有 C(64, 8) = 4426165368 種盤面要產，明顯的程式會跑很久QQ

而兩個皇后放在同個 row 或 column 上一定會互攻，所以只需在每個 row 或 column 擺放一個皇后就好：

int dfs(int row) {
  if (row == 8) return 1;
  
  int sum = 0;
  for (int col = 0; col < 8; col++)
    if (check(row, col)) {
      board[row] = col;
      sum += dfs(row + 1);
    }
  
  return sum;
}

這邊的 check() 就是本節的主題了，
在轉移狀態(例如盤面)前，若能預感(?)這狀態不是想要的，就中斷轉移，然後 backtrack 到原狀態，繼續進行別的狀態轉移

check() 將返回 true 或 false，以判定是否要 backtrack
有點幾何知識的話，會發現 check() 只需要 就能做到：

bool check(r2, c2) {
  for (int r1 = 0; r1 < r2; r1++) {
    int c1 = board[r1];
    if (c1 == c2 || c1-c2 == r1-r2 || c1-c2 == r2-r1) return false;
  }
  
  return true;
}

枚舉的盤面會少於 N! 很多，因為 check() 剪掉了許多不必再繼續遞迴下去的 DFS 樹枝。

練習：
UVa OJ 524 Prime Ring Problem
UVa OJ 211 The Domino Effect

子集生成

顧名思義，就是將 set 的所有子集挑出來
例如 的子集為

遞迴法

void powerset(int dep) {
  if(dep == N) {
    for (int i = 0; i < N; i++) printf("%d ", bit[i]);
    putchar('\n');
    return;
  }
  
  bit[dep] = 1;
  powerset(dep+1);
  bit[dep] = 0;
  powerset(dep+1);
}

N = 3 將輸出：

1 1 1 
1 1 0 
1 0 1 
1 0 0 
0 1 1 
0 1 0 
0 0 1 
0 0 0 

二進制法

for (int i = 0; i < (1<<N); i++) {
  for (int p = 0; p < N; p++) printf("%d ", bool(i&(1<<p)));
  putchar('\n');
}

N = 3 將輸出：

0 0 0
1 0 0 
0 1 0 
1 1 0 
0 0 1 
1 0 1 
0 1 1 
1 1 1 

在許多場合，我們不一定只有 0 和 1 兩種佔位符，可能有三種甚至更多
所以遞迴法比二進制法還要更為泛用。

下次一樣做搜尋，改天見！